#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 100+6;
const int maxa = 25000+7;
int a[maxa], dp[maxa];
int n;
int main() {
  int t; cin>>t;
  while(t--) {
    cin>>n; for(int i=0; i<n; ++i) cin>>a[i];
    memset(dp, 0, sizeof(dp));
    sort(a, a+n);
    int ans = n;
    dp[0] = 1;
    for(int i=0; i<n; ++i) {
      if(dp[a[i]]) {
        ans--;
      }
      else {
        for(int j=a[i]; j<maxa; j++) {
          dp[j] = dp[j] | dp[j - a[i]];
        }
      }
    }
    cout<<ans<<'\n';
  }
}
